10465 - Homer Simpson/10465.cpp

   1 #include <iostream>
   2
   3 #define MAX(a,b) ((a)>(b)?(a):(b))
   4
   5 using namespace std;
   6
   7 //Este problema se puede modelar como una mochila de capacidad t.
   8 //Tengo objetos de tamaño m y n.
   9 //Encontrar cuál es la capacidad máxima que puedo usar de la mochila.
  10 //(O en otras palabras, minimizar el espacio desperdiciado de la mochila)
  11 //Encontrar la mayor cantidad posible de objetos que me permitan usar la
  12 //capacidad máxima posible de la mochila.
  13
  14
  15 //x[i] : Maxima capacidad que puedo gastar con los objetos m y n que no exceda i
  16 //y[i] : Maxima cantidad de objetos que puedo utilizar para gastar una capacidad x[i]
  17 int x[10001], y[10001];
  18
  19 int main(){
  20   int m, n, t;
  21   while (cin >> m >> n >> t){
  22     x[0] = 0; //La maxima capacidad que puedo utilizar que no exceda 0 es 0, porque 1 < m,n
  23     y[0] = 0; //Para lograrlo utilizo 0 objetos
  24     for (int i=1; i<=t; ++i){
  25       x[i] = x[i-1]; //Puedo usar al menos la misma capacidad que podía antes...
  26       y[i] = y[i-1]; //Utilizando la misma cantidad de objetos que podía antes...
  27
  28       if (i-m >= 0 && x[i-m] + m <= i){
  29         if (x[i-m] + m > x[i]){ //Si la capacidad que gasto usando el objeto m es mayor que la actual...
  30           x[i] = x[i-m] + m;
  31           y[i] = y[i-m] + 1;
  32         }
  33       }
  34       if (i-n >= 0 && x[i-n] + n <= i){
  35         if (x[i-n] + n > x[i]){ ////Si la capacidad que gasto usando el objeto n es mayor que la actual..
  36           x[i] = x[i-n] + n;
  37           y[i] = y[i-n] + 1;
  38         }
  39       }
  40
  41       if (i-n >= 0 && i - m >= 0 &&
  42           x[i-n] + n == x[i-m] + m){ //Si gasto la misma capacidad escogiendo como ultimo objeto m o n...
  43         y[i] = MAX(y[i-m] + 1, y[i-n] + 1); //entonces la cantidad de objetos debe ser la máxima de las dos posibles
  44       }
  45     }
  46     //cout << "La maxima capacidad que puedo usar es: " << x[t] << endl;
  47     //cout << "Utilizo " << y[t] << " objetos" << endl;
  48     cout << y[t];
  49     if (x[t] < t){
  50       cout << " " << t - x[t] << endl;
  51     }else
  52     cout << endl;
  53   }
  54   return 0;
  55 }